Năm 25 tuổi (1965) Fryman ký hợp đồng với Pittsburgh Pirates. Ông ra mắt với tư cách tay ném dự bị cho Pirates vào năm 1966. Tuy vậy sau này ông bắt đầu được huấn luyện viên sử dụng nhiều hơn trong vai trò tay ném xuất phát. Ông đạt thành tích 12 thắng 9 thua, với tỉ lệ earned run average là 3.81 trong mùa giải đầu tiên, trong đó có ba trận shutout liên tiếp lần lượt trước Philadelphia Phillies,[1] New York Mets và Chicago Cubs.[2] Trận shutout trước Mets là một trận đấu gần như hoàn hảo khi Ron Hunt của Mets ghi điểm single trong hiệp 1, tuy nhiên không thành công trong nỗ lực steal chốt 2. Fryman loại cả 26 batter tiếp theo của Mets và không cho bất cứ batter nào có cơ hội trở thành baserunner.[3]

Thành tích của ông giảm xuống còn 3 thắng-8 thua (4.05 ERA) vào mùa giải 1967. Mùa giải sau đó ông cùng với các đồng đội Bill Laxton, Don Money và Harold Clem ký hợp đồng với Philadelphia Phillies để thay thế cho Jim Bunning, người chuyển sang Pirates theo chiều ngược lại.